package uk.ac.strath.cis.metric_spaces.indices;

import java.util.HashSet;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;

import uk.ac.strath.cis.metric_spaces.framework.AbstractMetricIndex;
import uk.ac.strath.cis.metric_spaces.framework.Distance;
import uk.ac.strath.cis.metric_spaces.framework.MetricIndex;

/**
 * @author Robert
 *
 * @param <E>
 */
public class BurkhardKellerTree<E> extends AbstractMetricIndex<E> {

    private E root;
    private final Map<Double, BurkhardKellerTree<E>> children = new TreeMap<Double, BurkhardKellerTree<E>>();

    /**
     * @param d
     */
    public BurkhardKellerTree(Distance<E> d) {
        super(d);
    }

    /**
     * @param copy
     * @param element
     */
    public BurkhardKellerTree(BurkhardKellerTree<E> copy, E element) {
        super(copy);
        insert(element, this);
    }

    /**
     * @param copy
     * @param element
     */
    public BurkhardKellerTree(BurkhardKellerTree<E> copy) {
        super(copy);
    }
    
    /* (non-Javadoc)
     * @see uk.ac.strath.cis.rmoss.metric_spaces.framework.AbstractMetricIndex#insert(java.util.Set)
     */
    public void insert(Set<E> elements) {
        super.insert(elements);
        for (E e : elements) {
            insert(e, this);
        }
    }

    private void insert(E element, BurkhardKellerTree<E> node) {
        if (node.root == null) {
            node.root = element;
        } else {
            double distance = distance(node.root, element);
            BurkhardKellerTree<E> child = node.children.get(distance);
            if (child == null) {
                node.children.put(distance, new BurkhardKellerTree<E>(this,
                        element));
            } else {
                insert(element, child);
            }
        }
    }

    /* (non-Javadoc)
     * @see uk.ac.strath.cis.rmoss.metric_spaces.framework.MetricIndex#rangeQuery(java.lang.Object, double)
     */
    public Set<E> rangeQuery(E element, double radius) {
        Set<E> returnSet = new HashSet<E>();
        rangeQuery(returnSet, element, this, radius);
        return returnSet;

    }

    private void rangeQuery(Set<E> returnSet, E element,
            BurkhardKellerTree<E> tree, double radius) {
        double distance = distance(element, tree.root);
        if (radius - distance >= 0.0) {
            returnSet.add(tree.root);
        }
        for (Double i : tree.children.keySet()) {
            if ((distance - radius <= i) && (i <= distance + radius)) {
                BurkhardKellerTree<E> bkt = tree.children.get(i);
                rangeQuery(returnSet, element, bkt, radius);
            }
        }
    }

    private String toString(StringBuilder sb, BurkhardKellerTree<E> node) {
        if (node == null) {
            return "";
        }
        sb.append(node.root);
        if (!node.children.isEmpty()) {
            sb.append("(");
            int i = 0;
            for (BurkhardKellerTree<E> child : node.children.values()) {
                toString(sb, child);
                if (i < node.children.values().size() - 1) {
                    sb.append(",");
                }
                i++;
            }
            sb.append(")");
        }
        return sb.toString();
    }

    /* (non-Javadoc)
     * @see java.lang.Object#toString()
     */
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        return this.toString(sb, this);
    }
    
    @Override
    public MetricIndex<E> clone() {
    	return new BurkhardKellerTree<E>(this);
    }
}
